//-------------------------------------------------------------------
// Purpose: Demonstrate how infix expressions can be parsed 
//          using a simple recursive descent parser.
// Author:  John Gauch
//-------------------------------------------------------------------

#include <cstdlib>
#include <iostream>
using namespace std;
bool TRACE = false;

char nextchar(string input, int &pos) 
{ 
   if (pos < int(input.length()))
      return input[pos]; 
   else 
      return ' ';
}

void readchar(string input, int &pos) 
{ 
   if (pos < int(input.length()))
      pos++; 
}

bool factor(string input, int &pos)
{
   if (TRACE) cout << "Entering factor\n";
   bool result = false;

   while ((nextchar(input, pos) >= '0') && (nextchar(input, pos) <= '9'))
   {
      readchar(input, pos);
      result = true;
   }

   if (TRACE) cout << "Leaving factor\n";
   return result;
}

bool rest_factor(string input, int &pos)
{
   if (TRACE) cout << "Entering rest_factor\n";
   bool result = true;

   if ((nextchar(input, pos) == '*') || (nextchar(input, pos) == '*'))
   {
      readchar(input, pos);
      if (factor(input, pos))
	 result = rest_factor(input, pos);
      else
	 result = false;
   }

   if (TRACE) cout << "Leaving rest_factor\n";
   return result;
}

bool term(string input, int &pos)
{
   if (TRACE) cout << "Entering term\n";
   bool result = false;

   if (factor(input, pos))
      result = rest_factor(input, pos);

   if (TRACE) cout << "Leaving term\n";
   return result;
}

bool rest_term(string input, int &pos)
{
   if (TRACE) cout << "Entering rest_term\n";
   bool result = true;

   if ((nextchar(input, pos) == '+') || (nextchar(input, pos) == '-'))
   {
      readchar(input, pos);
      if (term(input, pos))
	 result = rest_term(input, pos);
      else
	 result = false;
   }

   if (TRACE) cout << "Leaving rest_term\n";
   return result;
}

bool expression(string input)
{
   if (TRACE) cout << "Entering expression\n";
   bool result = false;

   int pos = 0;
   if (term(input, pos))
      result = rest_term(input, pos);

   if (TRACE) cout << "Leaving expression\n";
   return result;
}

int main()
{
   string message[] = { "invalid", "valid" };
   cout << "\nTesting expression\n";
   string input = "2+3*5";
   cout << "expression(" << input << ") = " << message[expression(input)] << endl;
   input = "6*4+1";
   cout << "expression(" << input << ") = " << message[expression(input)] << endl;
   input = "1-2*3-4";
   cout << "expression(" << input << ") = " << message[expression(input)] << endl;
   input = "9/8-7/6";
   cout << "expression(" << input << ") = " << message[expression(input)] << endl;
   input = "1+2++6";
   cout << "expression(" << input << ") = " << message[expression(input)] << endl;
   input = "3*/4-7";
   cout << "expression(" << input << ") = " << message[expression(input)] << endl;
   input = "123-45";
   cout << "expression(" << input << ") = " << message[expression(input)] << endl;
}